package n3211;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {

	static HashMap<String, Integer[]> map = new HashMap<String, Integer[]>();
	
	static int[][] ar=new int[10][100];
	
	static int f[]=new int[50001];
	
	static int solve()
	{
		int count=0;
		for(Iterator<String> it=map.keySet().iterator();it.hasNext();)
		{
			String key=it.next();
			Integer[] value=map.get(key);
			int sum=0;
			for(int i=0;i<value[1];i++)
			{
				sum+=ar[value[0]][i];
			}
			int sum2=sum>>1;
			for(int i=0;i<sum2+1;i++)f[i]=0;
			for(int i=0;i<value[1];i++)
			{//01背包问题
				for(int j=sum2;j>=ar[value[0]][i];j--)
				{
					if(f[j]<f[j-ar[value[0]][i]]+ar[value[0]][i])f[j]=f[j-ar[value[0]][i]]+ar[value[0]][i];
				}
			}
			count=count+sum-f[sum2];
		}
		return count;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception{

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		String line=null;
		while((line=bf.readLine())!=null)
		{
			StringTokenizer st=new StringTokenizer(line);
			int n1=Integer.parseInt(st.nextToken());
			int n2=Integer.parseInt(st.nextToken());
			if(n1==0&&n2==0)break;
			int global=0;
			map.clear();
			line=bf.readLine();
			st=new StringTokenizer(line);
			for(int i=0;i<n1;i++)//color
			{
				String color=st.nextToken();
				Integer[] value=new Integer[2];
				value[0]=global++;
				value[1]=0;
				map.put(color, value);
			}
			//pieces
			for(int i=0;i<n2;i++)
			{
				line=bf.readLine();
				st=new StringTokenizer(line);
				int t=Integer.parseInt(st.nextToken());
				String color=st.nextToken();
				Integer[] value=map.get(color);
				ar[value[0]][value[1]]=t;
				value[1]++;
				//map.put(color, value);
			}
			System.out.println(solve());
		}
	}

}
